package complexite;

import java.util.Collections;

public class QuickSelect3 {

	
	public static void faireTriInsertion(ExtArrayList az, int deb, int fin){
	    boolean bRetour = false;
	    int cpt;
	    int i;
	    int lg = fin + 1;
	    int Val;
	    
	    for(i = deb + 1; i < lg ; i++)
	    {    
	        Val = az.get(i);
	        cpt = i-1;
	        do
	        {
	            bRetour = true;
	            if(az.get(cpt) > Val)
	          {    
	            	az.set(cpt+1,az.get(cpt));
	                cpt = cpt-1;
	                bRetour = false;
	            }
	            if(cpt <0)
	            {
	                bRetour = true;
	            }
	        }while(!bRetour);
	        az.set(cpt+1,Val);     
	    }
	}
	
	public static void echange (ExtArrayList az,int num1,int num2){
		Collections.swap(az, num1,num2);
	}
	
	
	
	public static void select(ExtArrayList A,int first, int last, int i) {
		  
		 /* n is the number elements to select from */
		int  n = last - first + 1;
		
		if (i > n){
			System.err.println("element recherché en dehors du tableau");
			System.exit(1) ;
		}   
		
		if(n <= 20){
			
			faireTriInsertion(A, first, last);
			echange(A, first+i-1, first);
		}
		if(n > 20)
		{
			/********** main recursion *************************/
		    int numGroups = (int)Math.floor(n / 5);     /* integer division, round down */
		    for (int group = 0 ; group <  numGroups-1 ; ++group){
		         int shift = group*5;
		         //on trie le morceau du tableau
		         faireTriInsertion(A,first+shift,first+shift+4);
		         //on swap la mediane de ce morceau, pour la mettre ailleur
		         echange(A, first+shift +2,first + group );
		    }
		     
		    int lastMedian = first+numGroups-1;
		    /* now the medians of the numGroups groups are all A[first .. lastMedian] */
		     
		    /****** the first recursive call to find median of medians ******/
		    select(A, first, lastMedian, (int)Math.floor(numGroups / 2));
		    /* now median of medians is in slot A[first] */
		    /*********** partition array *********************/
		    int k = RandomQuickSelect.PartitionR(A,first, last,first);   /* See partition on page 146 of text */
		    /* now k is the index where the median of median winds up, the smaller elements */
		    /* will be in A[first..k-1] and larger elements will be in A[k+1..last] */
		    

		    
		    /************ where is the ith smallest element? ********/
		    if (k == first + i -1) {
		        /* ith smallest is the median of medians in A[k] */
		        echange(A,k,first);
		        return;
		        
		    } 
		    else if (k >= first + i -1) {
		        /* second recursion to find ith smallest among the "small" keys in A[first..k-1] */
		        select(A, first, k-1, i);
		    } 
		    else /* k < first + i -1 */ {
		        /* second recursion to find the proper element among the "large" keys */
		        int numSmaller = k-first+1; /* the number of "smaller" keys not recursed on */
		        
		        int newi = i - numSmaller;
		        /* the ith smallest of A[first..last] is the newi smallest of A[k+1..last] */
		        select(A, k+1, last, newi);
		        /* ith smallest now in A[k+1], put it in A[first] */
		        echange(A,k+1,first);
		    }
		}
	}


	public static void main(String[] args) {
		ExtArrayList az = new ExtArrayList();
		az.getArray(31001, 10, 600000);
		//System.out.println("de base     : " +az);
		//System.out.println(Selection(az,0,az.size()-1,(az.size() + 1) / 2 -1));
		select(az,   0   ,     az.size()-1    ,     ((az.size() + 1)/ 2));
		System.out.println("select median      :" + az.get(0));
		//System.out.println(az);
		Collections.sort(az);
		System.out.println("qsort  median      :" + az.get(   (az.size()) / 2   )    );
		//System.out.println(az);
//		faireTriInsertion(az, 0, az.size() - 1);
		

	}
	
	
	
	
	
	

}
